perm filename FLA3[DOC,TOB] blob
sn#012068 filedate 1971-12-13 generic text, type T, neo UTF8
00100 We describe a formal representation for a class of primitive
00200 three-dimensional shapes. These primitive representations are
00300 combined into compound articulated representations of familiar
00400 objects. With regard to primitive representations, we discuss
00500 only the formalism, not the inference of such descriptions from
00600 visual data for complex scenes. The primary design criteria for a
00700 representation are the ease with which we can recognize an object as
00800 essentially similar to another we have seen before, or the ease with
00900 which we can identify that objects with distinct differences have
01000 important similarities (a child and an adult, or a man and a woman).
01100 This is one basis for generalization. A representation is intended
01200 to express low-level knowledge about shape, i.e. class knowledge
01300 about familiar shapes, and to serve as a basis for approximation of
01400 shape, and conjecture about missing information, for example, the
01500 hidden half of objects. The primary criterion is not the simplicity
01600 of inference from visual data, although that is important. There
01700 are representations which are simple to obtain; arrays of intensity
01800 values, polynomial coefficients, Fourier or Hadamard transforms. For
01900 these representations to be useful in understanding complex scenes,
02000 they must be embedded in systems which use knowledge to accomplish
02100 segmentation of a scene into objects, and which make a separation of
02200 variables to represent similarities and differences rather than
02300 lumping all variables together in a distance measure. No single
02400 theory or representation will solve the problems of understanding a
02500 visual scene or the general problems of intelligence. The choice
02600 of representations depends on the task; special cases and privileged
02700 knowledge will always be important. This representation is not
02800 meant to be general or a unique and ultimate form of visual
02900 representation. At best it has some intuitive appeal as an example
03000 for the task of describing the approximate shape of a complex object.
03100 That task is a reasonable internal task for an intelligent being who
03200 hopes to remember shape and behavior of an object to be better
03300 prepared for a repeat encounter.
03400 This work is a background to work being carried out with G.J.
03500 Agin. We use a triangulation ranging device consisting of a laser
03600 and TV camera. Figure 1 shows the apparatus, in operation since
03700 January 1971. The ranging error is about 2 mm at 1 meter. The
03800 camera observes the position along the ray from the laser; that
03900 uniquely fixes position. In essence, it is stereo for which we can
04000 guarantee correspondence. A cylindrical lens deflects the beam into
04100 a plane of light, and a front surface mirror on a stepping motor
04200 deflects the plane of light over the scene. The basic realization,
04300 which was reached independently by Shirai [1], is that there is no
04400 ambiguity introduced by using a plane of light, instead of a ray of
04500 light. Consequently, speed is enormously increased and the
04600 deflection simplified. For the following discussion, the visual data
04700 we are assuming are 3-dimensional data. The problem we have set
04800 is to store descriptions of objects and recognize previously seen
04900 objects; that is, the programs build their own representations,
05000 rather than use externally given models.
05100 We work toward providing examples of effective use of visual
05200 memory and partial knowledge, i.e. context, partial views, associated
05300 noises, etc. Some necessary facilities for a visual memory are:
05400 a representation of shape and other properties
05500 structure/function heuristics of the significance of
05600 shape
05700 representation of space
05800 a referencing scheme which quickly references entries
05900 in very large memories, from partial views
06000 of an object
06100 a mechanism to test the hypotheses generated by
06300 memory reference; a playback mechanism which
06500 presumably uses the visual apparatus.
06550 At another time, we will describe our work in representation of space
06650 and methods for referencing descriptions in a visual memory.
06800 Visual representations play a significant part in human
06900 intelligence. Our model of immediate reality, which guides our
07000 motions and avoidance of objects, is intensely visual. Low-level
07100 three-dimensional representations appear in the visual cortex [2];
07200 this is one example of the representation of space. Luria [3]
07300 describes a mnemonist who created a visual imagery with rich
07400 associations to use the visual memory for non-visual tasks. Shepard
07500 [4] finds introspective reports and suggestive data to support a
07600 hypothesis of mental rotation of internal models in some shape
07700 comparison experiments. We are accustomed to making visual models
07800 for mathematical structures (after which we cover our tracks by
07900 formalizing) and in chess. Dreams apparently use the visual
08000 apparatus for some important purpose. Graphs and
08100 intensity-modulated display of three-dimensional data are important
08200 tools for understanding relations in data that tables cannot convey.
08300 Vision deals with richly-structured domains of knowledge; within
08400 geometry, we can make strong connections among data and assumptions.
08500 Consequently, problem-solving, to exploit most of these relations, is
08600 an important part of vision. However, problem-solving requires
08700 adequate representations; where problem-solving deals with rich
08800 models of geometry, visual representations are important examples.
08900
09000 REPRESENTATION OF PRIMITIVE ELEMENTS
09100 The representation of primitive elements allows a simple
09200 description of a broad class of shapes. We include in our compound
09300 representations other primitives more simply described by other
09400 representations, such as spheres, surfaces, and special case
09500 primitives. The inclusion of part/whole articulation in compound
09600 representations introduces inherent redundancy into descriptions. We
09700 will always have a choice of parts; some choices will be markedly
09800 simpler than others, and will be preferred by a simplicity criticism
09900 mechanism. In general, there will be several representations,
10000 even for simple cases, and we will need to carry a few redundant
10100 descriptions. Redundancy implies choice; we can regard it as an
10200 advantage that we have a choice of representations and can choose a
10300 simple one in special but usual cases.
10400 We will gain insight by considering the Blum representation
10500 [5]. It is more useful to describe that description in a slightly
10600 more general way than usual, as a spherical neighborhood transform,
10700 rather than in terms of the Blum transform. Consider the maximal
10800 spherical neighborhood at each point, defined as the largest
10900 spherical neighborhood centered at a point which lies entirely within
11000 the figure. Refer to figure 2 for an example. Keep only
11100 those maximal spherical neighborhoods not completely contained in
11200 other maximal spherical neighborhoods. The minimal set of maximal
11300 neighborhoods is a faithful representation of the figure. The
11400 spherical transform of a hemisphere is not at all simple, but if we
11500 allow choice and provide another mechanism instead of the unique
11600 transform, we can describe the hemisphere as a sphere and a cut. For
11700 dimension three and higher, the set of centers of the minimal set of
11800 maximal neighborhood, called the skeleton, is a surface or
11900 hypersurface. The spherical transform is composed of overlapping
12000 neighborhoods. In the representation described below, the
12100 neighborhoods are disjoint, and the axis is naturally a space curve,
12200 both of which have considerable intuitive value. The representation
12300 is locally defined, thus it is insensitive to obscurations of distant
12400 parts, while the Blum transform is quite sensitive to obscuration of
12500 the boundaries.
12600 We base our representation of primitive elements on
12700 generalized translational invariance, which we now define. The usual
12800 meaning of translational invariance is that an object transforms into
12900 itself along some translation. That can only be true for infinitely
13000 long general cylinders, that is, cylinders with arbitrary cross
13100 section. Consider a cross section X(p_,n_) through a point p_ and
13200 normal to the vector n_. The class of general cylinders can be
13300 described by invariance with respect to translation along n_:
13400 T(tn_) X(p_,n_) = X(p_+tn_,n_) , (1) for a unique
13500 direction n_ and arbitrary distance t. T(tn_) is the transform
13600 corresponding to translation by the vector tn_. We would like to
13700 extend the description. If we write:
13800 R(tα) T(tn_) X(p_,n_) = X(p_+tn_) , (2) where R is a
13900 rotation linear in t about a unique axis parallel to n_, we can
14000 generate another class of figures, general helices. A drill contains
14100 a portion of such a shape. These global descriptions are a small
14200 class.
14300 If we make the descriptions local, then we can describe
14400 shapes locally. A finite cylinder can be described by subsidiary
14500 inequalities corresponding to cuts by planes. But we can
14600 also write a differential generating relation:
14700 S T(εn_) X(p_,n_) = X(p_+εn_,Sn_) , (3) where S is a
14800 transformation not containing a translation. The meaning of the
14900 relation is that if we translate a cross section, then apply a
15000 normalizing transformation, the resulting cross section is identical
15100 to the cross section at the translated position. The relation
15200 applies to the repeated application of the operations over a limited
15300 range:
15400 X(p_(t),n_(t)) = integral S(α) T(dα*n_(α))X(p_(α),n_(α)) ,(4)
15600 0 ≤ t ≤ λ.
15650 We discuss a few examples for visualization.
15800 If S is a constant scale function, then condition (3) defines
15900 cones of arbitrary cross section. Figure 3 shows cross sections of
16000 a cylinder and figure 4 shows cross sections of a cone. However, if S
16100 is a scale function that depends on t, we can speak of locally
16200 conical or piecewise locally conical shapes, depending on the
16300 continuity of S.
16400 If S contains a rotation about an axis along the direction of
16500 translation, the corresponding shape is locally helical or piecewise
16600 locally helical, and may contain a scale function, in which case the
16700 shape is locally spiral (for example, a tapered drill). All
16800 these shapes are generated by a straight line along n_. We can
16900 choose S to include a rotation about an axis normal to n_, giving
17000 shapes generated along a space curve. A toroid is generated by a
17100 constant rotation about an axis normal to n_ (with no rotation about
17200 an axis parallel to n_ and unity scale function). The space curve
17300 may be non-planar if the axis normal to n_ is allowed to change
17400 direction.
17500 Helices are special cases of shapes with cross sections which
17600 change along the axis (depend on the parameter t). We can consider
17700 separate scale functions along orthogonal directions, particularly
17800 about an axis of bilateral symmetry. In general, S includes
17900 homeomorphisms of the cross sections.
18000 We may specify a space curve which forms the "spine" of the
18100 representation. Generalized translational invariance does not
18200 necessarily define a unique space curve. Presumably, the spine
18300 should pass through fixed points of S, but these are not necessarily
18400 unique. For a cylinder, any line in the direction of translational
18500 invariance is equivalent, while for a helix, a unique axis is
18600 defined. We are free to choose a space curve within the limits
18700 defined by translational invariance from the description of the cross
18800 section.
18900 The representation of a sphere is unattractive, requiring a
19000 locally conical representation without any preferred axis. That is
19100 not distressing, because for any portion of a sphere, we can choose a
19200 spherical representation.
19300 In general, we don't expect to have analytic descriptions of
19400 the cross section valued function, or the space curve called the
19500 spine. As with description of surfaces and plane curves, a
19600 useful description is to segment, describing segments with low-order
19700 curves.
19800 We must also look at the redundancy of descriptions. A block
19900 (rectangular parallelipiped) has three separate representations as a
20000 cylinder, in addition to representations along non-cylindrical axes,
20100 with shape-changing cross section. In this case, we can ignore all
20200 non-cylindrical representations and choose a single cylindrical
20300 description (e.g. that with the longest axis). In general,
20400 we won't be able to make a unique choice. That means at most a
20500 factor of two increase in storage, which won't affect the general
20600 behavior of mechanisms suitable for large memories.
20700 There are some relations which are not included explicitly in
20800 the representation. There is no convenient way to know whether a
20900 portion of a snake passes near another portion. That is the
21000 general problem of proximity in three dimensions. In fact, our
21100 description is one-dimensional, in the sense that we cannot tell
21200 proximity in two dimensions conveniently.
21300 The topic of complex representations is a topic to be
21400 discussed separately.
21500